{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Nodes With Value One"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #值为 1 的节点数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个&nbsp;<strong>无向&nbsp;</strong>树，有 <code>n</code> 个节点，节点标记为从 <code>1</code> 到 <code>n</code>&nbsp;，还有&nbsp;<code>n - 1</code> 条边。给定整数 <code>n</code>。标记为 <code>v</code> 的节点的父节点是标记为&nbsp;<code>floor (v / 2)</code>&nbsp;的节点。树的根节点是标记为 <code>1</code> 的节点。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果 <code>n = 7</code>，那么标记为 <code>3</code> 的节点将标记&nbsp;<code>floor(3 / 2) = 1</code> 的节点作为其父节点，标记为 <code>7</code> 的节点将标记&nbsp;<code>floor(7 / 2) = 3</code> 的节点作为其父节点。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你还得到一个整数数组 <code>queries</code>。最初，每个节点的值都是 <code>0</code>。对于每个查询 <code>queries[i]</code>，您应该翻转节点标记为&nbsp;<code>queries[i]</code> 的子树中的所有值。</p>\n",
    "\n",
    "<p>在&nbsp;<strong>处理完所有查询后</strong>，返回<em>值为 <code>1</code> 的节点总数。</em></p>\n",
    "\n",
    "<p><b>注意</b>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>翻转节点的值意味着值为 <code>0</code> 的节点变为 <code>1</code>，反之亦然。</li>\n",
    "\t<li><code>floor(x)</code>&nbsp;相当于将 <code>x</code> 舍入到最接近的整数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/19/ex1.jpg\" style=\"width: 600px; height: 297px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 5 , queries = [1,2,5]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 上图显示了执行查询后的树结构及其状态。蓝色节点表示值 0，红色节点表示值 1。\n",
    "在处理查询之后，有三个红色节点 (值为 1 的节点): 1、3、5。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/19/ex2.jpg\" style=\"width: 650px; height: 88px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 3, queries = [2,3,3]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong> 上图显示了执行查询后的树结构及其状态。蓝色节点表示值 0，红色节点表示值 1。\n",
    "在处理查询之后，有一个红色节点 (值为 1 的节点): 2。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries[i] &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-nodes-with-value-one](https://leetcode.cn/problems/number-of-nodes-with-value-one/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-nodes-with-value-one](https://leetcode.cn/problems/number-of-nodes-with-value-one/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[1,2,5]', '3\\n[2,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfNodes(self, n: int, queries: List[int]) -> int:\n",
    "        values = [0] * (n + 1)\n",
    "        count = [0] * (n + 1)\n",
    "        \n",
    "        for q in queries:\n",
    "            values[q] = 1 - values[q]\n",
    "            count[q] += 1\n",
    "        \n",
    "        # 计算每个节点的实际值\n",
    "        def computeValue(v):\n",
    "            total = values[v]\n",
    "            while v > 1:\n",
    "                v //= 2\n",
    "                total += count[v]\n",
    "            return total % 2\n",
    "        \n",
    "        result = 0\n",
    "        for i in range(1, n + 1):\n",
    "            result += computeValue(i)\n",
    "        \n",
    "        return result\n",
    "\n",
    "# 此方法的时间复杂度为O(n*len(queries))，其中n是节点数，len(queries)是查询数。\n",
    "# 这是因为对于每个查询，我们只更新一个节点的值和count值，然后在最后计算每个节点的实际值。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfNodes(self, n: int, queries: List[int]) -> int:\n",
    "        \"\"\"翻转子树后1的个数\"\"\"\n",
    "\n",
    "        def dfs(cur: int, pre: int) -> None:\n",
    "            nonlocal dfsId\n",
    "            starts[cur] = dfsId\n",
    "            for next in adjList[cur]:\n",
    "                if next != pre:\n",
    "                    dfs(next, cur)\n",
    "            ends[cur] = dfsId\n",
    "            dfsId += 1\n",
    "\n",
    "        adjList = [[] for _ in range(n)]\n",
    "        for cur in range(1, n):\n",
    "            parent = (cur - 1) // 2\n",
    "            adjList[parent].append(cur)\n",
    "            adjList[cur].append(parent)\n",
    "\n",
    "        starts, ends, dfsId = [0] * n, [0] * n, 0\n",
    "        dfs(0, -1)\n",
    "\n",
    "        diff = [0] * (n + 1)\n",
    "        for node in queries:\n",
    "            node -= 1\n",
    "            left, right = starts[node], ends[node]\n",
    "            diff[left] ^= 1\n",
    "            diff[right + 1] ^= 1\n",
    "        diff = list(accumulate(diff, lambda x, y: x ^ y))\n",
    "        return sum(diff[i] & 1 for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfNodes(self, n: int, queries: List[int]) -> int:\n",
    "        def dfs(u, rev_cnt):\n",
    "            if u > n: return 0\n",
    "            rev_cnt += rev[u]\n",
    "            return dfs(u * 2, rev_cnt) + dfs(u * 2 + 1, rev_cnt) + (rev_cnt & 1)\n",
    "        rev = Counter(queries)\n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfNodes(self, n: int, queries: List[int]) -> int:\n",
    "        ct = Counter(queries)\n",
    "        def dfs(i, j):\n",
    "            if i <= n:\n",
    "                x = j + ct[i] & 1\n",
    "                return x + dfs(i*2, x) + dfs(i*2+1, x)\n",
    "            return 0\n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfNodes(self, n: int, queries: List[int]) -> int:\r\n",
    "        cnt = Counter(queries)\r\n",
    "        \r\n",
    "        def dfs(node: int, c: int) -> int:\r\n",
    "            if node > n: return 0\r\n",
    "            nc = (c + cnt[node]) % 2\r\n",
    "            ans = nc\r\n",
    "            ans += dfs(node * 2, nc)\r\n",
    "            ans += dfs(node * 2 + 1, nc)\r\n",
    "            return ans\r\n",
    "            \r\n",
    "        return dfs(1, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
